﻿#include <iostream>
#define MAX(a, b) (a > b ? a : b)

/**
 * 获取指定的十进制位
 * @param number
 * @param digitBit
 * @return
 */
static int getDigitBitNumber(int number, int digitBit) {
    if (digitBit == 1) return number % 10;

    return (number % (int) (pow(10, digitBit))) / (int) (pow(10, digitBit - 1));
}

/**
 * 获取指定的数字的最高十进制位
 * @param number
 * @return
 */
static int getMaxDigitBit(int number) {
    int digitBit = 1;
    while (number / 10 != 0) {
        number /= 10;
        ++digitBit;
    }

    return digitBit;
}

static int getMaxNumber(int* numbers, const size_t size) {
    int maxNumber = numbers[0];
    for (int i = 1; i < size; i++) {
        maxNumber = MAX(maxNumber, numbers[i]);
    }

    return maxNumber;
}

static void radixSort(int* numbers, const int left, const int right, const int maxDigitBit) {
    size_t assistantArraySize = right-left+1;
    int* assistantArr = (int*)malloc(assistantArraySize*sizeof(int));
    memset(assistantArr, 0, assistantArraySize*sizeof(int));

#define BUCKET_COUNT 10
    int bucket[BUCKET_COUNT];
    memset(bucket, 0, sizeof(int)*BUCKET_COUNT);
    
    for (int digitBit = 1; digitBit <= maxDigitBit; digitBit++) {

        for (int i = 0; i < BUCKET_COUNT; i++) {
            bucket[i] = 0;
        }

        for (int i = left; i <= right; i++) {
            int number = getDigitBitNumber(numbers[i], digitBit);
            bucket[number]++;
        }

        for (int i = 1; i < BUCKET_COUNT; i++) {
            bucket[i] = bucket[i - 1] + bucket[i];
        }

        for (int i = right; i >= left; i--) {
            int number = getDigitBitNumber(numbers[i], digitBit);
            int index = bucket[number] - 1;
            assistantArr[index] = numbers[i];
            bucket[number]--;
        }

        for (int i = left; i <= right; i++) {
            numbers[i] = assistantArr[i - left];
        }
    }

    free(assistantArr);
}

/** 桶排序
  * [13,27,35,19,50,69,100,8]
  * 每个数字补足3位数，[013,027,035,019,050,069,100,008]
  * 先按照个位数入桶；然后再按照十位数入桶；最后按照百位数入桶
  * 这个地方的桶用的数据结构是队列
  * Step1: 按照个位数
  * 0     1  2  3     4  5     6  7     8     9
  * [100] [] [] [013] [] [035] [] [027] [008] [019]
  * [050] [] [] []    [] []    [] []    []    [069]
  * 依次出桶：[100,050,013,035,027,008,019,069]
  *
  * Step2: 按照十位数
  * 0     1     2     3     4  5     6     7  8  9
  * [100] [013] [027] [035] [] [050] [069] [] [] []
  * [008] [019] []    [] [] [] []    []    [] [] []
  * 依次出桶：[100,008,013,019,027,035,050,069]
  *
  * Step3: 按照百位数
  * 0     1     2  3  4  5  6  7  8  9
  * [008] [100] [] [] [] [] [] [] [] []
  * [013] []    [] [] [] [] [] [] [] []
  * [019] []    [] [] [] [] [] [] [] []
  * [027] []    [] [] [] [] [] [] [] []
  * [035] []    [] [] [] [] [] [] [] []
  * [050] []    [] [] [] [] [] [] [] []
  * [069] []    [] [] [] [] [] [] [] []
  * 依次出桶：[008,013,019,027,035,050,069,100]
  */
int main_RadixSort()
{
    int arr[] = {13, 27, 35, 19, 15, 44, 50, 69, 100, 8};
    size_t size = sizeof(arr)/sizeof(int);
    int max = getMaxNumber(arr, size);
    int maxDigitBit = getMaxDigitBit(max);
    radixSort(arr, 0, size - 1, maxDigitBit);

    for (int i = 0; i < size; i++) {
        printf("arr[%d]=%d\n", i, arr[i]);
    }
    
    return 0;
}